Chapter 8. 그래프(Graphs)

(줄리아 학습 노트)

데이터 전처리

8.1 최다 빈도 연결점 시각화

Colon before a variable name creates a symbol

(Symbols) The : character has two syntactic purposes in Julia. The first form creates a Symbol, an interned string used as one building-block of expressions:

https://docs.julialang.org/en/v1/manual/metaprogramming/

:green과 같이 :이 앞에 붙은 문자열은 Symbol(심볼) 타입이다. Symbol 타입은 문자열보다 효율적이며 ID나 키로 사용할 수 있다. Symbol은 서로 붙일 수 없으며 프로그램 전체에서 상수로 사용할 때 정의한다.(데이터 프레임의 컬럼명(열 헤더) 또한 Symbol 이다.)

Julia 프로그래밍 (에이콘 출판사, 2015)

2. 최단거리 찾기 문제 (Shortest path problem)

그래프 생성 원리를 알기 위해 이번에는 하나의 그래프씩 출력해 보았다.

위의 그래프를 한 번에 그리면 아래와 같이 그려진다.

3. 최소 스패닝 트리 (Minimum Spanning Tree, MST)

시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 즉, 가장 낮은 가중치를 먼저 선택한다. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html

4. 페이지 랭크(page lank)

https://ko.wikipedia.org/wiki/%ED%8E%98%EC%9D%B4%EC%A7%80%EB%9E%AD%ED%81%AC

https://sungmooncho.com/2012/08/26/pagerank/

위의 두 그래프를 합치면

5. 군집 계수(Clustering Coefficients)

Finally...

After finishing this notebook, you should be able to:

(강의 자료 원문 내용)

🥳 One cool finding

We ran PageRank (which is a common algorithm to rank nodes in a network), and visualized the PageRank values on the US airports. The results agreed with the hypothesis that known hubs have higher PageRank value. Look at Atlanta, it's actually the biggest.